# note: code is wrong
import sys
class Solution(object):
    def getStepNum(self, number):
        # print(number)
        if number == 1:
            return 1
        if number == 2:
            return 2
        if number % 3 == 0:
            return 1 + self.getStepNum(number // 3)
        if (number - 1) % 3 == 0:
            return 1 + self.getStepNum(number - 1)
        if number % 2 == 0:
            return 1 + self.getStepNum(number // 2)
        return 1 + self.getStepNum(number - 1)

if __name__ == "__main__":
    s = Solution()
    f = sys.stdin
    cnt = int(f.readline())
    for i in range(cnt):
        line = int(f.readline())
        print(s.getStepNum(line))

